package com.zwj.interview.链表;


/**
 * 如果一个链表中包含环，那么应该如何找出环的入口节点？从链表的头节点开始顺着next指针方向进入环的第1个节点为环的入口节点
 */
public class 获取链表中环的起点 {

    ListNode detectCycle(ListNode head) {
        ListNode fast, slow;
        fast = slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            //fast和slow相遇的时候，说明有环
            if (fast == slow) {
                break;
            }
        }
        //走到这里说明根本没环
        if (fast == null || fast.next == null) {
            // fast 遇到空指针说明没有环
            return null;
        }
        //慢指针重新指向头结点
        slow = head;
        // 快慢指针同步前进，相交点就是环起点
        while (slow != fast) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }





}
